#!/usr/bin/python
import Image

global bx, by, img, im
global n
global fs

def solved(cur):
    global by
    if cur[1]+1 >= by:
        return True
    return False

def isOut(cur):
    global im, bx, by
    if cur[0]<0 or cur[0]>=bx:
        return True
    if cur[1]<0 or cur[1]>=by:
        return True
    if im[cur[0], cur[1]] != (255, 255, 255, 255):
        return True
    return False

def pSolution(path):
    global n
    open('solution%d.txt'%n, 'wb').write('\n'.join(','.join(map(str,k[0])) for k in path))
    n+=1

def cleanImg():
    img = Image.open('maze.png')
    im = img.load()
    
    bx,by = img.size    # borders
    # deal left up area
    for x in range(bx):
        for y in range(by):
            if im[x,y] == (127,127,127,255):
                im[x,y] = (255,255,255,255)
                
    img.save('maze_clean.png')

def init():
    global bx, by, img, im, fs
    global n
    img = Image.open('maze_clean.png')
    #img = Image.open('test/test.png')
    im = img.load()
    
    bx,by = img.size    # borders
    
    n = 0

def main():
    global bx, by, img, im, fs
    
    init()
    # solve the maze
    
    r = lambda c: (c[0]+1, c[1])
    d = lambda c: (c[0], c[1]+1)
    l = lambda c: (c[0]-1, c[1])
    u = lambda c: (c[0], c[1]-1)
    fs = [r, d, l, u]
    
    prefi = lambda x:(x-1)<0 and 3 or x-1
    nextfi = lambda x:(x+1)%4
    revfi = lambda x:x in (1,3) and 4-x or 2-x
    
    path = [[(0, 0),revfi(1),prefi(1)]]
    while len(path):
        cur = path[-1][0]
        fi = path[-1][2]
        #print path
        #raw_input()
        if solved(cur):
            pSolution(path)
            return
            path.pop()
            continue
        
        flag = False
        while fi != path[-1][1]:
            path[-1][2] = nextfi(fi)
            nextcur = fs[fi](cur)
            if not isOut(nextcur):
                path.append([nextcur, revfi(fi), prefi(fi)])
                flag = True
                break
            fi = nextfi(fi)
            
        if not flag:
            path.pop()
            continue

if __name__ == '__main__':
    main()
